package ks;

public class ShortestPath_FLOYD {
    private int[][] W;
    private int[][] D;
    public final static int INFINITY = Integer.MAX_VALUE;

    public void floyd(MGraph G) {
        int vexNum = G.getVexNum();
        // 路径矩阵（D）
        D = new int[vexNum][vexNum];
        // 前驱表（P）
        W = new int[vexNum][vexNum];
        // 初始化D,P
        for (int i = 0; i < vexNum; i++) {
            for (int j = 0; j < vexNum; j++) {
                D[i][j] = G.getArcs()[i][j];
                W[i][j] = j;
            }
        }
        // 循环 中间经过顶点
        for (int k = 0; k < vexNum; k++) {
            // 循环所有路径
            for (int m = 0; m < vexNum; m++) {
                for (int n = 0; n < vexNum; n++) {
                    int mn = D[m][n];
                    int mk = D[m][k];
                    int kn = D[k][n];
                    int addedPath = (mk == INFINITY || kn == INFINITY) ? INFINITY : mk + kn;
                    if (mn > addedPath) {
                        // 如果经过k顶点路径比原两点路径更短，将两点间权值设为更小的一个
                        D[m][n] = addedPath;
                        // 前驱设置为经过下标为k的顶点
                        W[m][n] = W[m][k];
                    }

                }
            }
        }
    }

    public int[][] getD() {
        return D;
    }

    public int[][] getW() {
        return W;
    }
}
